home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 301-325 / disk_319 / cnewssrc / cnews.orig.lzh / contrib / dbz next >
Internet Message Format  |  1989-06-27  |  9KB
  1. From utgpu!jarvis.csri.toronto.edu!mailrus!sharkey!b-tech!zeeff Tue Feb  7 17:1
  2. :31 EST 1989
  3. Article: 1900 of news.software.b:
  4. Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!sharkey!b-tech!zeeff
  5. From: zeeff@b-tech.ann-arbor.mi.us (Jon Zeeff)
  6. Newsgroups: news.software.b
  7. Subject: Re: Dbz and news 2.11
  8. Message-ID: <5095@b-tech.ann-arbor.mi.us>
  9. Date: 4 Feb 89 18:56:09 GMT
  10. References: <20@bungia.Bungia.MN.ORG>
  11. Reply-To: zeeff@b-tech.ann-arbor.mi.us (Jon Zeeff)
  12. Distribution: usa
  13. Organization: Branch Technology Ann Arbor, MI
  14. Lines: 322
  15.  
  16. In article <20@bungia.Bungia.MN.ORG> ahby@bungia.MN.ORG (Shane P. McCarron) wri
  17. es:
  18. >Some time ago the dbz sources were posted for use with news 2.11.
  19. >Patches have been posted, and a number of sites are using these
  20. >routines to make news run faster on machines without dbm libraries.  I
  21. >seem to remember some controversy surrounding the use of these
  22. >routines.  Something about their containing AT&T proprietary stuff?  I
  23. >realize that by asking this I am going to get a hundred answers, all
  24. >of them different.  What I am really looking for is ONE AUTHORITATIVE
  25. >ANSWER.  Can anyone out there say for sure whether this code is freely
  26. >distributable or not?
  27.  
  28. As the author, I suppose I can supply an authorative answer.  Dbz 
  29. contains no AT&T code at all.  The only thing in it not written by me 
  30. is the hashing, and that is taken from pathalias (with permission).  
  31.  
  32. Here it is if anyone missed it:
  33.  
  34.  
  35. /*
  36. dbz.c  V1.5
  37.  
  38. Copyright 1988 Jon Zeeff (umix!b-tech!zeeff)
  39. You can use this code in any manner, as long as you leave my name on it
  40. and don't hold me responsible for any problems with it.
  41.  
  42. Hacked on by gdb@ninja.UUCP (David Butler); Sun Jun  5 00:27:08 CDT 1988
  43.  
  44. These routines replace dbm as used by the usenet news software
  45. (it's not a full dbm replacement by any means).  It's fast and
  46. simple.  It contains no AT&T code.
  47.  
  48. BSD sites will notice some savings in disk space.  Sys V sites without
  49. dbm will notice much faster operation.
  50.  
  51. Note: .pag files created by version 1.[0-3] need to be recreated before
  52.       using this version.
  53.  
  54. This code relies on the fact that news stores a pointer to the history
  55. file as the dbm data.  It doesn't store another copy of the key like
  56. dbm does so it saves disk space.  All you can do is fetch() and
  57. store() data.
  58.  
  59. Just make news with the DBM option and link with dbz.o.
  60. */
  61.  
  62. /*
  63.    Set this to the something several times larger than the maximum # of
  64.    lines in a history file.  It should be a prime number.
  65. */
  66. #define INDEX_SIZE 99991L
  67.  
  68. #define DEBUG if (0) printf              /* for no debugging */
  69. /* #define DEBUG if (1) printf          /* for debugging */
  70. /* #define DEBUG if (debug) printf        /* for "rn" type debugging */
  71.  
  72. /* Note: let the optimizer remove any if(0) or if(1) code above */
  73.  
  74. #include <fcntl.h>
  75. #include <string.h>
  76. #include <ctype.h>
  77.  
  78. long lseek();
  79.  
  80. static long get_ptr();
  81. static int put_ptr();
  82. static void lcase();
  83. static long hash();
  84. static void crcinit();
  85.  
  86. typedef struct {
  87.     char *dptr;
  88.     int dsize;
  89. } datum;
  90.  
  91. static int Data_fd;        /* points to /usr/lib/news/[n]history */
  92. static int Index_fd = -1;    /* points to /usr/lib/news/[n]history.pag */
  93.  
  94. int 
  95. dbminit(name)
  96. char *name;
  97. {
  98.         char index_file[1024];    /* index file name */
  99.     void crcinit();
  100.  
  101.     if (Index_fd >= 0) {
  102.         DEBUG("dbminit: dbminit aready called once\n");
  103.         return(-1);    /* init already called once */
  104.     }
  105.  
  106.     strcpy(index_file, name);
  107.     strcat(index_file, ".pag");
  108.  
  109.     /* if we don't have permission to open the pag file for read/write */
  110.     /* then we may never attempt a store().  If we do, it will fail */
  111.  
  112.     if ((Index_fd = open(index_file, O_RDWR)) < 0 &&
  113.         (Index_fd = open(index_file, O_RDONLY)) < 0 &&
  114.         (Index_fd = open(index_file, O_CREAT | O_RDWR, 0644)) < 0) 
  115.     {
  116.         DEBUG("dbminit: Index_file open failed\n");
  117.         return(-1);
  118.     }
  119.  
  120.     if ((Data_fd = open(name, O_RDONLY)) < 0) {
  121.  
  122.         /* The only time the data file does not exist is when */
  123.         /* expire is running (as "news") and it is ok to create it */
  124.         /* If we don't have "permission" the create will fail, too */
  125.  
  126.         if (close(creat(name, 0644)) < 0 ||
  127.             (Data_fd = open(name, O_RDONLY)) < 0) {
  128.             DEBUG("dbminit: Data_file open failed\n");
  129.             close(Index_fd);
  130.             Index_fd = -1;
  131.             return(-1);
  132.         }
  133.     }
  134.  
  135.     crcinit();    /* initialize the crc table */
  136.     DEBUG("dbminit: succeeded\n");
  137.     return(0);
  138. }
  139.  
  140. int
  141. dbmclose()
  142. {
  143.     if (Index_fd >= 0) {
  144.         close(Index_fd);
  145.         Index_fd = -1;
  146.         close(Data_fd);
  147.     }
  148.     DEBUG("dbmclose: succeeded\n");
  149.     return(0);
  150. }
  151.  
  152. /* get an entry from the database */
  153. datum
  154. fetch(key)
  155. datum key;
  156. {
  157.     long index_ptr;
  158.     long index_size = INDEX_SIZE;
  159.         char buffer[1024];
  160.     static long data_ptr;
  161.     datum output;
  162.     long hash();
  163.     long get_ptr();
  164.     void lcase();
  165.  
  166.     DEBUG("fetch: (%s)\n", key.dptr);
  167.  
  168.     for (index_ptr = hash(key.dptr, key.dsize);
  169.         --index_size && (data_ptr = get_ptr(index_ptr)) >= 0L;
  170.         index_ptr = ++index_ptr % INDEX_SIZE) {
  171.  
  172.         lseek(Data_fd, data_ptr, 0);
  173.         read(Data_fd, buffer, (unsigned)key.dsize);
  174.  
  175.         /* key should be lcase version of article id and no tab */
  176.  
  177.         lcase(buffer, key.dsize);
  178.         if (buffer[key.dsize - 1] == '\t') {
  179.             buffer[key.dsize - 1] = '\0';
  180.         }
  181.  
  182.         DEBUG("fetch: buffer (%s)\n", buffer);
  183.         if (strncmp(key.dptr, buffer, key.dsize) == 0) {
  184.             /* we found it */
  185.             output.dptr = (char *)&data_ptr;
  186.             output.dsize = sizeof(long);
  187.             DEBUG("fetch: successful\n");
  188.             return(output);
  189.         }
  190.     }
  191.  
  192.     /* we didn't find it */
  193.  
  194.     output.dptr = (char *)0;
  195.     output.dsize = 0;
  196.     DEBUG("fetch: failed\n");
  197.     return(output);
  198. }
  199.  
  200. /* add an entry to the database */
  201. store(key, data)
  202. datum key;
  203. datum data;
  204. {
  205.     /* lint complains about a possible pointer alignment problem here */
  206.     /* it is not a problem because dptr is the first element of a */
  207.     /* structure and should be aligned for anything */
  208.     DEBUG("store: (%s, %ld)\n", key.dptr, *((long *)data.dptr));
  209.     return(put_ptr(hash(key.dptr, key.dsize), *((long *)data.dptr)));
  210. }
  211.  
  212. /* get a data file pointer from the specified location in the index file */
  213.  
  214. static long
  215. get_ptr(index_ptr)
  216. long index_ptr;
  217. {
  218.     long data_ptr;
  219.  
  220.     DEBUG("get_ptr: (%ld)\n", index_ptr);
  221.  
  222.     /* seek to where it should be */
  223.     lseek(Index_fd, (long)(index_ptr * sizeof(long)) ,0);
  224.  
  225.     /* read it */
  226.     if (read(Index_fd, (char *)&data_ptr, sizeof(long)) != sizeof(long) ||
  227.         data_ptr == 0L) {
  228.         DEBUG("get_ptr: failed\n");
  229.         return(-1L);
  230.     }
  231.     DEBUG("get_ptr: succeeded\n");
  232.     return(--data_ptr);    /* remove the offset we added in put_ptr */
  233. }
  234.  
  235. /* put a data file pointer into the specified location in the index file */
  236. /* move down further if slots are full (linear probing) */
  237. static
  238. put_ptr(index_ptr, data_ptr)
  239. long index_ptr;
  240. long data_ptr;
  241. {
  242.     long get_ptr();
  243.     long index_size = INDEX_SIZE;
  244.  
  245.     /* find an empty slot */
  246.     while (--index_size && get_ptr(index_ptr) >= 0L) {
  247.         index_ptr = ++index_ptr % INDEX_SIZE;
  248.     }
  249.  
  250.     if (index_size == 0L) {
  251.         DEBUG("put_ptr: hash table overflow - failed\n");
  252.         return(-1);
  253.     }
  254.  
  255.     /* seek to spot */
  256.     lseek(Index_fd, (long)(index_ptr * sizeof(long)), 0);
  257.  
  258.     ++data_ptr;   /* add one so that we can use 0 as no pointer */
  259.  
  260.     /* write in data */
  261.     if (write(Index_fd, (char *)&data_ptr, sizeof(long)) != sizeof(long)) {
  262.         DEBUG("put_ptr: write failed\n");
  263.         return(-1);
  264.     }
  265.  
  266.     DEBUG("put_ptr: succeeded\n");
  267.     return(0);
  268. }
  269.  
  270. static void
  271. lcase(s, n)
  272. register char *s;
  273. register int n;
  274. {
  275.     for (; n > 0; --n, ++s) {
  276.         *s = tolower(*s);
  277.     }
  278. }
  279.  
  280. /* This is a simplified version of the pathalias hashing function.
  281.  * Thanks to Steve Belovin and Peter Honeyman
  282.  *
  283.  * hash a string into a long int.  31 bit crc (from andrew appel).
  284.  * the crc table is computed at run time by crcinit() -- we could
  285.  * precompute, but it takes 1 clock tick on a 750.
  286.  *
  287.  * This fast table calculation works only if POLY is a prime polynomial
  288.  * in the field of integers modulo 2.  Since the coefficients of a
  289.  * 32-bit polynomial won't fit in a 32-bit word, the high-order bit is
  290.  * implicit.  IT MUST ALSO BE THE CASE that the coefficients of orders
  291.  * 31 down to 25 are zero.  Happily, we have candidates, from
  292.  * E. J.  Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
  293.  *    x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
  294.  *    x^31 + x^3 + x^0
  295.  *
  296.  * We reverse the bits to get:
  297.  *    111101010000000000000000000000001 but drop the last 1
  298.  *         f   5   0   0   0   0   0   0
  299.  *    010010000000000000000000000000001 ditto, for 31-bit crc
  300.  *       4   8   0   0   0   0   0   0
  301.  */
  302.  
  303. #define POLY 0x48000000L    /* 31-bit polynomial (avoids sign problems) */
  304.  
  305. static long CrcTable[128];
  306.  
  307. static void
  308. crcinit()
  309. {    register int i, j;
  310.     register long sum;
  311.  
  312.     for (i = 0; i < 128; ++i) {
  313.         sum = 0L;
  314.         for (j = 7 - 1; j >= 0; --j)
  315.             if (i & (1 << j))
  316.                 sum ^= POLY >> j;
  317.         CrcTable[i] = sum;
  318.     }
  319.     DEBUG("crcinit: done\n");
  320. }
  321.  
  322. static long
  323. hash(name, size)
  324. register char *name;
  325. register int size;
  326. {
  327.     register long sum = 0L;
  328.  
  329.     while (size--) {
  330.         sum = (sum >> 7) ^ CrcTable[(sum ^ (*name++)) & 0x7f];
  331.     }
  332.     DEBUG("hash: returns (%ld)\n", sum % INDEX_SIZE);
  333.     return(sum % INDEX_SIZE);
  334. }
  335.  
  336. -- 
  337.   Jon Zeeff            zeeff@b-tech.ann-arbor.mi.us
  338.   Ann Arbor, MI            mailrus!b-tech!zeeff
  339.  
  340.  
  341.